package Linkedlists;
import java.util.*;

public class Partition {
    /*
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class PalindromeList {
        public boolean chkPalindrome(ListNode A) {
            // write code here
            ListNode head=A;
            ListNode fast=head;
            ListNode slow=head;
            while(fast!=null&&fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
            }
            //翻转
            ListNode cur=slow.next;
            while(cur!=null){
                ListNode curN=cur.next;
                cur.next=slow;
                slow=cur;
                cur=curN;
            }
            //判断是否回文
            while(head!=slow){
                if(head.val!=slow.val){
                    return false;
                }
                if(head.next==slow){
                    return true;
                }
                head=head.next;
                slow=slow.next;
            }
            return true;
        }
    }
}
